package sorting;

import java.util.Arrays;

/**
 * An integer sorting algorithm, to use when we can bound the value of the items.
 * Its running time is linear in the number of items and the difference between the maximum and minimum key values,
 * so it is only suitable for direct use in situations where the variation in keys is not significantly greater than
 * the number of items
 * <p>
 * Time complexity: O(n+k), where n=a.size, and k=high-low+1
 * Space complexity: O(n)
 */
public class CountSort {

    public static int[] countSort(int[] a, int low, int high) {
        // for each cell will hold the number of times that (value-low) repeats
        int[] counts = new int[high - low + 1];
        for (int x : a)
            counts[x - low]++; // - low so the lowest possible value is always in location 0

        // so count[x] holds the number of time the number in position x in the sorted set appears in a
        int current = 0;
        // technically a new array is not needed !!! can do directly on a
        int[] b = new int[a.length];
        for (int i = 0; i < counts.length; i++) {
            // fills counts[i] elements of value i + low in current
            Arrays.fill(b, current, current + counts[i], i + low);
            current += counts[i]; // leap forward by counts[i] steps
        }
        return b;
    }

    public static void main(String[] args) {
        int[] a = {4, 1, 4, 1, 5, 6, 4, 1};
        int[] b = countSort(a, 1, 6);
    }
}
